package com.ieslab.backtracking;

/**
 * n皇后问题的递归解法
 */
public class QueenProblemRecurision {
	private static int count = 0; // 解的个数
	static final int queenCount = 4; // 皇后的数量
	static int[] a = new int[queenCount + 1];
	static int[] b = new int[queenCount + 1]; // 记录棋盘上的n个列的占用情况
	static int[] c = new int[2 * queenCount + 1]; // 2n-1个主对角线的占用情况
	static int[] d = new int[2 * queenCount + 1]; // 2n-1个负对角线的占用情况

	public static void main(String[] args) { // 下标从1开始，不是从0开始
		// 初始化,java中数组元素的值默认为数据类型(int)的默认值0
		trySearch(1);
	}

	private static void output() {
		count++;
		System.out.print("第" + count + "个解：");
		for (int k = 1; k <= queenCount; k++) {
			System.out.print(a[k] + ",");
		}
		System.out.println();
	}

	private static void trySearch(int queenNo) {
		for (int j = 1; j <= queenCount; j++) { // 第queenInd个皇后有n种可能的位置
			// 判断位置是否冲突
			if (b[j] == 0 && c[queenNo + j] == 0 && d[queenNo - j + queenCount] == 0) {
				a[queenNo] = j; // 摆放皇后
				b[j] = 1; // 占用第j列
				c[queenNo + j] = 1; // 占用2个对角线
				d[queenNo - j + queenCount] = 1;
				System.out.println("queenNo=" + queenNo + ",j=" + j + ",b[" + j + "]=1,c[" + (queenNo + j) + "]=1,d["
						+ (queenNo - j + queenCount) + "]=1");
				if (queenNo < queenCount) { // n个皇后没有摆完，递归摆放下一个皇后
					trySearch(queenNo + 1);
				} else if (queenNo == queenCount) {
					output(); // 完成任务，打印结果
				}
				// 回溯
				b[j] = 0;
				c[queenNo + j] = 0;
				d[queenNo - j + queenCount] = 0;
				System.out.println("b[" + j + "]=0,c[" + (queenNo + j) + "]=0,d[" + (queenNo - j + queenCount) + "]=0");
			}
		}
	}
}
